package 面试经典150题.哈希表;

import java.util.HashSet;

/**
 * @author tmh
 * @date 2024/6/4 20:24
 * @description
 */
public class T128最长连续序列 {

    /**
     * 具体过程如下：
     * <p>
     * 1、定义一个哈希表hash，将nums数组中的数都放入哈希表中。
     * 2、遍历哈希表hash，如果当前数x的前驱x-1不存在，我们就以当前数x为起点向后枚举。
     * 3、假设最长枚举到了数y，那么连续序列长度即为y-x+1。
     * 4、不断枚举更新答案。
     */
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int result = 0;
        for (Integer num : set) {
            if (!set.contains(num - 1)) {
                int y = num;
                //如果set里面含有y+1，那么y++
                while (set.contains(y + 1)) {
                    y++;
                }
                //y-num+1就是最后的答案
                result = Math.max(result, y - num + 1);
            }
        }
        return result;
    }
}
